package com.zp.self.module.level_4_算法练习.数据结构.数组;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_31_下一个排列 {
    //测试
    public static void main(String[] args) {
        int[] ints = {1,2,3};
        new 力扣_31_下一个排列().nextPermutation(ints);
        for (int anInt : ints) System.out.print(anInt + ",");
        System.out.println();

        ints = new int[]{3,2,1};
        new 力扣_31_下一个排列().nextPermutation(ints);
        for (int anInt : ints) System.out.print(anInt + ",");
        System.out.println();

        ints = new int[]{1,3,2};
        new 力扣_31_下一个排列().nextPermutation(ints);
        for (int anInt : ints) System.out.print(anInt + ",");
        System.out.println();

        ints = new int[]{1, 3, 4, 2, 6, 7, 8, 10};
        new 力扣_31_下一个排列().nextPermutation(ints);
        for (int anInt : ints) System.out.print(anInt + ",");
    }

    /**
    题目：找出这个数组排序出的所有数中，刚好比当前数大的那个数
     比如当前 nums = [1,2,3]。这个数是123，找出1，2，3这3个数字排序可能的所有数，
     排序后，比123大的那个数 也就是132
     如果当前 nums = [3,2,1]。这就是1，2，3所有排序中最大的那个数，
     那么就返回1，2，3排序后所有数中最小的那个，也就是1，2，3 -> [1,2,3]

     示例 1：

     输入：nums = [1,2,3]
     输出：[1,3,2]
     示例 2：

     输入：nums = [3,2,1]
     输出：[1,2,3]
     示例 3：

     输入：nums = [1,1,5]
     输出：[1,5,1]

    分析：【perfect】
       1.从后向前：a.只要前面的比后面的小，就需要位移.当前的最大值下标.
                   b.找到刚好比我大的元素，队列记录之前出现过的值，因为队列中的值是从小到大的
                    【可以优化为List,然后使用二分查找，更快一点】
                   c.交换后 ，从前面的节点开始排序.
            优化：
                    0.首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i] < a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n)【必然是下降序列。】
                   1.如果找到了顺序对，那么在区间 [i+1,n)中【从后向前查找第一个元素】 jj 满足 a[i] < a[j]。这样「较大数」即为 a[j]。
                   2.[i+1,n)[i+1,n) 必为降序。我们可以直接使用【双指针反转区间】[i+1,n)使其变为升序，而【无需对该区间进行排序】。

    边界值 & 注意点：
       1.已经是最大的了的花，需要返回最小值 : Arrays.sort(nums);
        测试案例未通过：[1,3,2] .原因：未找到刚好比numb[i]大的元素
     **/
    public void nextPermutation(int[] nums) {
        int index=nums.length-1;
        Queue<Integer> queue = new ArrayDeque<>();//记录出现过的值的下标，方便找出
        queue.add(index);
        boolean haveMax =false;
        for (int i = index-1; i>=0; i--) {
            //交换，并对 i之后的元素排序
            if(nums[i]<nums[index]){
                while (!queue.isEmpty()){
                    Integer poll = queue.poll();
                    if(nums[poll]>nums[i]){
                        nums[poll] = nums[poll] ^ nums[i];
                        nums[i] = nums[poll] ^ nums[i];
                        nums[poll] = nums[poll] ^ nums[i];
                        break;
                    }
                }
                //冒泡排序
                Arrays.sort(nums, i+1, nums.length);
                haveMax =true;
                break;
            }else {
                if(nums[queue.peek()] !=nums[i])
                    queue.add(i);
                index = i;
            }
        }
        if(!haveMax) Arrays.sort(nums);
    }
}
